home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / editors / emacs / xemacs / xemacs-1.004 / xemacs-1 / xemacs-19.13 / lisp / oobr / tree-x / draw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-08-26  |  34.7 KB  |  1,281 lines

  1. /* ----------------------------------------------------------------------------
  2.  * File    : draw.c
  3.  * Purpose : drawing-specific routines for dynamic tree program
  4.  * ----------------------------------------------------------------------------
  5.  */
  6.  
  7. #include <X11/Intrinsic.h>
  8. #include <X11/StringDefs.h>
  9.  
  10. #include "defs.h"
  11. #include "tree.h"
  12. #include "dbl.h"
  13. #include "intf.h"
  14.  
  15. /* ------------------------------------------------------------------------- */
  16. /*                Global Variables                             */
  17. /* ------------------------------------------------------------------------- */
  18.  
  19. Tree *TheTree;
  20.  
  21.  
  22. /* ------------------------------------------------------------------------- */
  23. /*                Local Variables                              */
  24. /* ------------------------------------------------------------------------- */
  25.  
  26. static char AnimationMode = FALSE;        
  27. static char strbuf[BUFSIZ];
  28. static int  AnimationStep = ANIMATION_STEP;
  29.  
  30. /* ------------------------------------------------------------------------- */
  31. /*             Forward Function Declarations                       */
  32. /* ------------------------------------------------------------------------- */
  33.  
  34. void DrawNode();
  35. void DrawTreeContour();
  36.  
  37.  
  38. /* ------------------------------------------------------------------------- */
  39. /*                   Functions                                 */
  40. /* ------------------------------------------------------------------------- */
  41.  
  42.  
  43. /* ----------------------------------------------------------------------------
  44.  * 
  45.  *   BeginFrame() provides an abstraction for double buffering. It should
  46.  *   be called prior to creating a new frame of animation.
  47.  * 
  48.  * ----------------------------------------------------------------------------
  49.  */
  50.  
  51. void
  52. BeginFrame()
  53. {
  54.   DBLbegin_frame(TreeDrawingAreaDB);
  55. }
  56.  
  57.  
  58. /* ----------------------------------------------------------------------------
  59.  * 
  60.  *   EndFrame() provides an abstraction for double buffering. It should
  61.  *   be called after creating a new frame of animation.
  62.  * 
  63.  * ----------------------------------------------------------------------------
  64.  */
  65.  
  66. void
  67. EndFrame()
  68. {
  69.   DBLend_frame(TreeDrawingAreaDB, 0);
  70. }
  71.  
  72.  
  73. /* ----------------------------------------------------------------------------
  74.  * 
  75.  *   GetDrawingSize() gets the size of the drawing area, and returns the
  76.  *   dimensions in the arguments.
  77.  * 
  78.  * ----------------------------------------------------------------------------
  79.  */
  80.  
  81. void
  82. GetDrawingSize(width, height)
  83.      int *width, *height;
  84. {
  85.   Dimension w, h;
  86.   
  87.   XtVaGetValues(TreeDrawingArea, 
  88.         XtNwidth, &w,
  89.         XtNheight, &h,
  90.         NULL);
  91.  
  92.   *width  = (int) w;
  93.   *height = (int) h;
  94. }
  95.  
  96.  
  97. /* ----------------------------------------------------------------------------
  98.  * 
  99.  *   SetDrawingSize() sets the size of the drawing area to the given
  100.  *   dimensions. 
  101.  * 
  102.  * ----------------------------------------------------------------------------
  103.  */
  104.  
  105. void
  106. SetDrawingSize(width, height)
  107.      int width, height;
  108. {
  109.   XtVaSetValues(TreeDrawingArea,
  110.         XtNwidth, (Dimension) width,
  111.         XtNheight,  (Dimension) height,
  112.         NULL);
  113. }
  114.  
  115.  
  116. /* ----------------------------------------------------------------------------
  117.  * 
  118.  *   SetDrawingTree() is used to specify what tree is to be drawn in the
  119.  *   drawing area. 
  120.  * 
  121.  * ----------------------------------------------------------------------------
  122.  */
  123.  
  124. void
  125. SetDrawingTree(tree)
  126.    Tree *tree;
  127. {
  128.    TheTree = tree;
  129. }
  130.  
  131.  
  132. /* ----------------------------------------------------------------------------
  133.  * 
  134.  *   SetNodeLabel() sets the label text of the specified node and computes
  135.  *   the bounding rectangle so that the layout can be determined. This
  136.  *   function is called when new nodes are created. If TreeAlignNodes is
  137.  *   True, the string is truncated so that the node's width is no longer
  138.  *   than TreeParentDistance.
  139.  * 
  140.  * ----------------------------------------------------------------------------
  141.  */
  142.  
  143. void
  144. SetNodeLabel(node, label)
  145.      Tree *node;
  146.      char *label;
  147. {
  148.   int         len;
  149.   int         dummy;
  150.   XCharStruct rtrn;
  151.   
  152.   len = strlen(label);
  153.   while (len > 1) {
  154.     XTextExtents(TreeLabelFont, label, len, &dummy, &dummy, &dummy, &rtrn);
  155.     node->width  = rtrn.lbearing + rtrn.rbearing + (LABEL_MAT_WIDTH * 2) + 1;
  156.     node->height = rtrn.ascent + rtrn.descent + (LABEL_MAT_HEIGHT * 2) + 1;
  157.     if (TreeAlignNodes) {
  158.       if (node->width <= (2 * TreeParentDistance))
  159.     break;
  160.       else
  161.     len--;
  162.     }
  163.     else
  164.       break;
  165.   }
  166.   
  167.   node->label.text = label;
  168.   node->label.len  = len;
  169.   node->label.xoffset = LABEL_MAT_WIDTH + 1,
  170.   node->label.yoffset = rtrn.ascent + LABEL_MAT_HEIGHT + 1;
  171. }
  172.  
  173.  
  174. /* ----------------------------------------------------------------------------
  175.  * 
  176.  *   SetDrawColor() sets the drawing color of the TreeDrawingArea. 
  177.  * 
  178.  * ----------------------------------------------------------------------------
  179.  */
  180.  
  181. void
  182. SetDrawColor(color)
  183.      int color;
  184. {
  185.   XSetForeground(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
  186.          TreeDrawingAreaDB->colors[color]);
  187. }
  188.  
  189. /* ----------------------------------------------------------------------------
  190.  * 
  191.  *   SetLineWidth() sets the line width of lines drawn in the TreeDrawingArea.
  192.  * 
  193.  * ----------------------------------------------------------------------------
  194.  */
  195.  
  196. void
  197. SetLineWidth(width)
  198.      unsigned int width;
  199. {
  200.   XSetLineAttributes(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
  201.              width, LineSolid, CapButt, JoinRound);
  202. }
  203.  
  204.  
  205. /* ----------------------------------------------------------------------------
  206.  * 
  207.  *   SetContours() sets the visibility of three possible contour modes: 
  208.  *   the outside contour, all subtree contours, or selected contours.
  209.  * 
  210.  * ----------------------------------------------------------------------------
  211.  */
  212.  
  213. void
  214. SetContours(option)
  215.      ContourOption option;
  216. {
  217.   if (option == NoContours) {
  218.     switch (TreeShowContourOption) {
  219.     case OutsideContour:
  220.       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, FALSE);
  221.       break;
  222.     case AllContours:
  223.       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
  224.       break;
  225.     case SelectedContours:
  226.       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, TRUE, TRUE);
  227.       break;
  228.     default:
  229.       ;
  230.     }
  231.     DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
  232.   }
  233.   else if (option == OutsideContour) {
  234.     switch (TreeShowContourOption) {
  235.     case AllContours:
  236.       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
  237.       break;
  238.     case SelectedContours:
  239.       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, TRUE, TRUE);
  240.       break;
  241.     default:
  242.       ;
  243.     }
  244.     DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
  245.   } else if (option == AllContours) {
  246.     DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, TRUE);
  247.   } else if (option == SelectedContours) {
  248.     switch (TreeShowContourOption) {
  249.     case AllContours:
  250.       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
  251.       break;
  252.     case OutsideContour:
  253.       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, FALSE);
  254.       break;
  255.     default:
  256.       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
  257.     }
  258.     DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, TRUE, TRUE);
  259.   }
  260.   TreeShowContourOption = option;
  261. }
  262.  
  263.  
  264. /* ----------------------------------------------------------------------------
  265.  * 
  266.  *   HiliteNode() is called by Unzip() to change the color of a node. 
  267.  * 
  268.  * ----------------------------------------------------------------------------
  269.  */
  270.  
  271. void
  272. HiliteNode(tree, pos_mode)
  273.      Tree *tree;
  274. {
  275.   SetDrawColor(HIGHLIGHT_COLOR);
  276.   DrawNode(tree, pos_mode);
  277.   SetDrawColor(TREE_COLOR);
  278. }
  279.  
  280.  
  281. /* ----------------------------------------------------------------------------
  282.  * 
  283.  *   DrawNode() takes a node and draws the node in the specified widget
  284.  *   at its (x,y) coordinate. (x, y) indicates the upper-left corner where
  285.  *   the node is drawn. Also, a line is drawn from the center of the left
  286.  *   edge to the center of the parent's right edge. 'draw_mode' specifies 
  287.  *   the drawing mode (whether or not the node is erased, rather than drawn).
  288.  *   'pos_mode' determines whether or not to use the old position of the node.
  289.  *   This flag is used in animating the movement of a node from its old
  290.  *   position to its new position.
  291.  * 
  292.  * ----------------------------------------------------------------------------
  293.  */
  294.  
  295. void
  296. DrawNode(node, pos_mode)
  297.      Tree     *node;
  298.      PosMode  pos_mode;
  299. {
  300.   Widget   w;
  301.   GC       gc;
  302.   
  303.   w  = TreeDrawingArea;
  304.   gc = TreeDrawingAreaDB->gc;
  305.   
  306.   if (pos_mode == Old) {
  307.     XDrawString(XtDisplay(w), XtWindow(w), gc,
  308.         node->old_pos.x + node->label.xoffset,
  309.         node->old_pos.y + node->label.yoffset,
  310.         node->label.text, node->label.len);
  311.     XDrawRectangle(XtDisplay(w), XtWindow(w), gc,
  312.            node->old_pos.x, node->old_pos.y,
  313.            node->width, node->height);
  314.     if (node->parent) 
  315.       XDrawLine(XtDisplay(w), XtWindow(w), gc,
  316.         node->old_pos.x - 1,
  317.         node->old_pos.y + (node->height / 2),
  318.         node->parent->old_pos.x + node->parent->width + 1,
  319.         node->parent->old_pos.y + (node->parent->height / 2));
  320.     if (node->elision) {
  321.       XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
  322.             FillTiled);
  323.       XFillRectangle(XtDisplay(w), XtWindow(w), gc,
  324.              node->old_pos.x + node->width - ELISION_WIDTH,
  325.              node->old_pos.y + 1, ELISION_WIDTH, node->height - 1);
  326.       XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
  327.             FillSolid);
  328.     }
  329.   } else {
  330.     XDrawString(XtDisplay(w), XtWindow(w), gc,
  331.         node->pos.x + node->label.xoffset,
  332.         node->pos.y + node->label.yoffset,
  333.         node->label.text, node->label.len);
  334.     
  335.     XDrawRectangle(XtDisplay(w), XtWindow(w), gc,
  336.            node->pos.x, node->pos.y,
  337.            node->width, node->height);
  338.     if (node->parent) 
  339.       XDrawLine(XtDisplay(w), XtWindow(w), gc,
  340.         node->pos.x - 1,
  341.         node->pos.y + (node->height / 2),
  342.         node->parent->pos.x + node->parent->width + 1,
  343.         node->parent->pos.y + (node->parent->height / 2));
  344.     if (node->elision) {
  345.       XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
  346.             FillTiled);
  347.       XFillRectangle(XtDisplay(w), XtWindow(w), gc,
  348.              node->pos.x + node->width - ELISION_WIDTH,
  349.              node->pos.y + 1, ELISION_WIDTH, node->height - 1);
  350.       XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
  351.             FillSolid);
  352.     }
  353.   }
  354. }
  355.  
  356.  
  357. /* ----------------------------------------------------------------------------
  358.  * 
  359.  *   DrawTreeContour() draws the contour of the specified subtree. Bridges
  360.  *   are not traversed, so the actual subtree contour is drawn, as opposed
  361.  *   to the merged contour. 'color' specifies the drawing color. If 'detach'
  362.  *   is True,  the lines attaching the subtree contour to the node are not
  363.  *   drawn.  If 'select' is true, then only subtrees that are flagged as
  364.  *   selected are shown. If 'recursive' is True, the entire tree is traversed.
  365.  * 
  366.  * ----------------------------------------------------------------------------
  367.  */
  368.  
  369. void
  370. DrawTreeContour(tree, pos_mode, color, detach, select, recursive)
  371.      Tree *tree;
  372.      PosMode pos_mode;
  373.      int color;
  374.      int detach;
  375.      int select;
  376.      int recursive;
  377. {
  378.   Widget w = TreeDrawingArea;
  379.   Polyline *contour, *tail;
  380.   Tree *child;
  381.   int x, y, i;
  382.  
  383.   if (tree == NULL)
  384.     return;
  385.  
  386.   if ((select && tree->show_contour) || !select) {
  387.  
  388.     SetDrawColor(color);
  389.     SetLineWidth(TreeContourWidth);
  390.    
  391.     /* draw upper contour */
  392.     contour = tree->contour.upper.head;
  393.     tail    = tree->contour.upper.tail;
  394.     if (pos_mode == Old) {
  395.       x = tree->old_pos.x - tree->border;
  396.       y = tree->old_pos.y - tree->border;
  397.     }
  398.     else {
  399.       x = tree->pos.x - tree->border;
  400.       y = tree->pos.y - tree->border;
  401.     }
  402.  
  403.     if (detach) {        /* skip over attaching lines */
  404.       for (i = 0 ; i < 2 ; i++) {
  405.     x += contour->dx;
  406.     y += contour->dy;
  407.     contour = contour->link;
  408.       }
  409.     }
  410.     
  411.     while (contour) {
  412.       XDrawLine(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc,
  413.         x, y, x + contour->dx, y + contour->dy);
  414.       x += contour->dx;
  415.       y += contour->dy;
  416.       if (contour == tail)    /* make sure you don't follow bridges */
  417.     contour = NULL;
  418.       else
  419.     contour = contour->link;
  420.     }
  421.  
  422.     /* draw lower contour */
  423.     contour = tree->contour.lower.head;
  424.     tail    = tree->contour.lower.tail;
  425.     if (pos_mode == Old) {
  426.       x = tree->old_pos.x - tree->border;
  427.       y = tree->old_pos.y + tree->border + tree->height;
  428.     } else {
  429.       x = tree->pos.x - tree->border;
  430.       y = tree->pos.y + tree->border + tree->height;
  431.     }
  432.  
  433.     if (detach) {        /* skip over attaching lines */
  434.       for (i = 0 ; i < 2 ; i++) {
  435.     x += contour->dx;
  436.     y += contour->dy;
  437.     contour = contour->link;
  438.       }
  439.     }
  440.  
  441.     while (contour) {
  442.       XDrawLine(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc,
  443.         x, y, x + contour->dx, y + contour->dy);
  444.       x += contour->dx;
  445.       y += contour->dy;
  446.       if (contour == tail)    /* make sure you don't follow bridges */
  447.     contour = NULL;
  448.       else
  449.     contour = contour->link;
  450.     }
  451.   }
  452.   
  453.   if (recursive) {
  454.     FOREACH_CHILD(child, tree)
  455.       if (!child->elision)
  456.     DrawTreeContour(child, pos_mode, color,
  457.             detach, select, recursive);
  458.   }
  459.  
  460.   SetDrawColor(TREE_COLOR);
  461.   SetLineWidth(0);
  462. }
  463.  
  464.  
  465. /* ----------------------------------------------------------------------------
  466.  * 
  467.  *   DrawTree() traverses the given tree, drawing the node and connecting
  468.  *   segments. The tree contours are also drawn at each step, if enabled.
  469.  *   'draw_mode' specifies the drawing mode in which the tree is drawn.
  470.  *   'pos_mode' determines whether or not to use the old position of the node.
  471.  *   This flag is used in animating the movement of a node from its old
  472.  *   position to its new position. DrawNode() is called to draw an individual 
  473.  *   node.
  474.  * 
  475.  * ----------------------------------------------------------------------------
  476.  */
  477.  
  478. void
  479. DrawTree(tree, pos_mode)
  480.      Tree     *tree;
  481.      PosMode  pos_mode;
  482. {
  483.   if (tree == NULL)
  484.     return;
  485.  
  486.   DrawNode(tree, pos_mode);
  487.  
  488.   /* do stuff that animates Unzip() */
  489.   if (tree->split) {
  490.     if (!AnimationMode ||
  491.     (tree->pos.x == tree->old_pos.x &&
  492.      tree->pos.y == tree->old_pos.y))
  493.       DrawTreeContour(tree, pos_mode, SPLIT_COLOR, FALSE, FALSE, FALSE);
  494.     else
  495.       DrawTreeContour(tree, pos_mode, ACTION_COLOR, FALSE, FALSE, FALSE);
  496.   }
  497.   if (tree->on_path)
  498.     HiliteNode(tree, pos_mode);
  499.  
  500.   if (tree->child && !tree->elision) 
  501.     DrawTree(tree->child, pos_mode);
  502.   if (tree->sibling)
  503.     DrawTree(tree->sibling, pos_mode);
  504. }
  505.  
  506.  
  507. /* ----------------------------------------------------------------------------
  508.  * 
  509.  *   ShiftTree() adjusts the positions of each node so that it moves from
  510.  *   the "old" position towards the "new position". This is used by
  511.  *   AnimateTree(). 'done' is set to FALSE if the tree is not in its
  512.  *   final position; it is used to determine when to stop animating the tree.
  513.  * 
  514.  * ----------------------------------------------------------------------------
  515.  */
  516.  
  517. void
  518. ShiftTree(tree, done)
  519.      Tree *tree;
  520.      int  *done;
  521. {
  522.   Tree *child;
  523.   
  524.   if (tree->old_pos.x != tree->pos.x ||
  525.       tree->old_pos.y != tree->pos.y)
  526.     {
  527.       tree->old_pos.x = tree->pos.x;
  528.       tree->old_pos.y = tree->pos.y;
  529.     }
  530.   
  531.   FOREACH_CHILD(child, tree)
  532.     ShiftTree(child, done);
  533. }
  534.  
  535.  
  536. /* ----------------------------------------------------------------------------
  537.  * 
  538.  *   AnimateTree() draws the given tree in a series of steps to give the
  539.  *   effect of animation from the "old" layout to the "new" layout of the
  540.  *   tree. 
  541.  * 
  542.  *   The algorithm used here is not efficient; the entire tree is drawn
  543.  *   on each iteration of the animation sequence; it would be more efficient
  544.  *   to only redraw what is necessary. However, the method used here takes
  545.  *   advantage of existing code without modification.
  546.  * 
  547.  * ----------------------------------------------------------------------------
  548.  */
  549.  
  550. void
  551. AnimateTree(tree)
  552.      Tree *tree;
  553. {
  554.   int done = FALSE;
  555.  
  556.   AnimationMode = FALSE;
  557.   /* highlight which nodes have to move */
  558.   BeginFrame();
  559.     DrawTree(tree, Old);
  560.   EndFrame();
  561.   Pause(); 
  562.   if (PauseAfterStep)
  563.     AnimationStep = ANIMATION_STEP_STEP;
  564.   while (!done) {
  565.     done = TRUE;
  566.     ShiftTree(tree, &done);
  567.     BeginFrame();
  568.       DrawTree(tree, Old);
  569.     EndFrame();
  570.     if (PauseAfterStep)
  571.       Pause();
  572.   }
  573.   if (PauseAfterStep)
  574.     AnimationStep = ANIMATION_STEP;
  575.   AnimationMode = FALSE;
  576. }
  577.  
  578.  
  579. /* ----------------------------------------------------------------------------
  580.  * 
  581.  *   AnimateZip() generates a sequence of frames that animates the Zip() step.
  582.  *   It is similar in logical structure to Zip().
  583.  * 
  584.  * ----------------------------------------------------------------------------
  585.  */
  586.  
  587. void 
  588. AnimateZip(tree)
  589.      Tree *tree;
  590. {
  591.   Tree *child;
  592.    
  593.   /* show results of Join() step */
  594.   if (tree->child) {
  595.     BeginFrame();
  596.       FOREACH_CHILD(child, tree)
  597.         child->split = FALSE;
  598.       DrawTree(TheTree, New);
  599.       DrawTreeContour(tree, New, CONTOUR_COLOR, TRUE, FALSE, FALSE);
  600.     EndFrame();
  601.  
  602.     StatusMsg("Zip: merge and join contours", FALSE);
  603.     Pause(); 
  604.    
  605.     /* show results of AttachParent() step */
  606.     BeginFrame();
  607.       DrawTree(TheTree, New);
  608.       DrawTreeContour(tree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
  609.     EndFrame();
  610.  
  611.     StatusMsg("Zip: attach parents", FALSE);
  612.     Pause(); 
  613.   }
  614.   
  615.   tree->on_path = FALSE;
  616.    
  617.   if (tree->parent)
  618.     AnimateZip(tree->parent);
  619.   else {
  620.     tree->on_path = FALSE;
  621.     BeginFrame();
  622.       DrawTree(TheTree, New);
  623.       DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
  624.     EndFrame();
  625.     StatusMsg("Zip: reassemble entire contour", FALSE);
  626.     Pause(); 
  627.   }
  628. }
  629.  
  630.  
  631. /* ----------------------------------------------------------------------------
  632.  * 
  633.  *   CountNodes() returns the number of nodes in the specified tree. 
  634.  *   Nodes below a node that has been collapsed are ignored. 
  635.  * 
  636.  * ----------------------------------------------------------------------------
  637.  */
  638.  
  639. int
  640. CountNodes(tree)
  641.      Tree *tree;
  642. {
  643.   int num_nodes = 1;        /* count root of subtree */
  644.   Tree *child;
  645.   
  646.   if (!tree->elision) {
  647.     FOREACH_CHILD(child, tree)
  648.       num_nodes += CountNodes(child);
  649.   }
  650.   return (num_nodes);
  651. }
  652.  
  653.  
  654. /* ----------------------------------------------------------------------------
  655.  * 
  656.  *   CollectNodeRectangles() is a recursive function used by
  657.  *   GetSubTreeRectangles() to collect the rectangles of descendant nodes
  658.  *   into the pre-allocated storage passed to this function.
  659.  * 
  660.  * ----------------------------------------------------------------------------
  661.  */
  662.  
  663. void
  664. CollectNodeRectangles(node, rectangles, fill)
  665.      Tree *node;
  666.      XRectangle **rectangles;
  667.      int fill;
  668. {
  669.   Tree *child;
  670.    
  671.   (*rectangles)->x = node->pos.x;
  672.   (*rectangles)->y = node->pos.y;
  673.   if (fill) {
  674.     (*rectangles)->width = node->width + 1;
  675.     (*rectangles)->height = node->height + 1;
  676.   } else {
  677.     (*rectangles)->width = node->width;
  678.     (*rectangles)->height = node->height;
  679.   }
  680.   (*rectangles)++;
  681.   
  682.   if (!node->elision)
  683.     FOREACH_CHILD(child, node) 
  684.       CollectNodeRectangles(child, rectangles, fill);
  685. }
  686.  
  687.  
  688. /* ----------------------------------------------------------------------------
  689.  * 
  690.  *   GetSubTreeRectangles() builds an array of XRectangles that contain
  691.  *   all the node rectangles in the tree, except the root node itself. 
  692.  *   The array is returned in 'rectangles' and the number of rectangles
  693.  *   is returned in 'nrectangles.' Storage for the rectangles is allocated
  694.  *   in this function. This function is used by PickAction to determine
  695.  *   what rectangles need to be dissolved away. 'fill', if True, specifies
  696.  *   that the rectangles should be 1 pixel larger in each dimension to 
  697.  *   compensate for FillRectangle behavior. 
  698.  * 
  699.  * ----------------------------------------------------------------------------
  700.  */
  701.  
  702. void
  703. GetSubTreeRectangles(tree, rectangles, nrectangles, fill)
  704.      Tree *tree;
  705.      XRectangle **rectangles;
  706.      int *nrectangles, fill;
  707. {
  708.   Tree *child;
  709.   XRectangle *crect;        /* current rectangle */
  710.   
  711.   *nrectangles = CountNodes(tree) - 1;        /* don't count root node */
  712.   *rectangles = (XRectangle *) malloc(sizeof(XRectangle) * *nrectangles);
  713.   ASSERT(*rectangles, "could not allocate memory for rectangles");
  714.   
  715.   crect = *rectangles;
  716.   if (!tree->elision)
  717.     FOREACH_CHILD(child, tree)
  718.       CollectNodeRectangles(child, &crect, fill);
  719. }
  720.  
  721.  
  722. /* ----------------------------------------------------------------------------
  723.  * 
  724.  *   CollectNodeSegments() is a recursive function used by GetSubTreeSegments()
  725.  *   to collect the line segments connecting nodes into the pre-allocated 
  726.  *   storage passed to this function.
  727.  * 
  728.  * ----------------------------------------------------------------------------
  729.  */
  730.  
  731. void
  732. CollectNodeSegments(node, segments)
  733.      Tree *node;
  734.      XSegment **segments;
  735. {
  736.   Tree *child;
  737.    
  738.   (*segments)->x1 = node->pos.x - 1;
  739.   (*segments)->y1 = node->pos.y + (node->height / 2),
  740.   (*segments)->x2 = node->parent->pos.x + node->parent->width + 1;
  741.   (*segments)->y2 = node->parent->pos.y + (node->parent->height / 2);
  742.   (*segments)++;
  743.  
  744.   if (!node->elision)
  745.     FOREACH_CHILD(child, node) 
  746.       CollectNodeSegments(child, segments);
  747. }
  748.  
  749.  
  750. /* ----------------------------------------------------------------------------
  751.  * 
  752.  *   GetSubTreeSegments() builds an array of XSegments that contain
  753.  *   all the line segments connecting the nodes in the tree. The array is
  754.  *   returned in 'segments' and the number of segments is returned in
  755.  *   'nsegments.' Storage for the segments is allocated in this function.
  756.  *   This function is used by PickAction to determine what line segments
  757.  *   rectangles need to be dissolved away.
  758.  * 
  759.  * ----------------------------------------------------------------------------
  760.  */
  761.  
  762. void
  763. GetSubTreeSegments(tree, segments, nsegments)
  764.      Tree *tree;
  765.      XSegment **segments;
  766.      int *nsegments;
  767. {
  768.   Tree *child;
  769.   XSegment *cseg;        /* current segment */
  770.  
  771.   *nsegments = CountNodes(tree) - 1;
  772.   *segments = (XSegment *) malloc(sizeof(XSegment) * *nsegments);
  773.   ASSERT(*segments, "could not allocate memory for segments");
  774.   
  775.   cseg = *segments;
  776.   if (!tree->elision)
  777.     FOREACH_CHILD(child, tree)
  778.       CollectNodeSegments(child, &cseg);
  779. }
  780.  
  781.  
  782. /* ----------------------------------------------------------------------------
  783.  * 
  784.  *   ComputeSubTreeExtent() computes the extent of a subtree. This is
  785.  *   easily computed based on the tree's contour, as in ComputeTreeSize().
  786.  *   This extent is stored in the node, and used by SearchTree for 
  787.  *   pick-correlation. 
  788.  * 
  789.  *   This function assumes that the given tree has at least one child; do not
  790.  *   pass a leaf node to this function. 
  791.  * 
  792.  * ----------------------------------------------------------------------------
  793.  */
  794.  
  795. void
  796. ComputeSubTreeExtent(tree)
  797.      Tree *tree;
  798. {
  799.   int width, height;
  800.   int x_offset, y_offset;
  801.  
  802.   ComputeTreeSize(tree, &width, &height, &x_offset, &y_offset);
  803.   tree->subextent.pos.x  = tree->child->pos.x - tree->child->border;
  804.   tree->subextent.pos.y  = tree->pos.y - y_offset;
  805.   tree->subextent.width  = width - (tree->child->pos.x - tree->pos.x) - 1;
  806.   tree->subextent.height = height - 1;
  807. }
  808.  
  809.  
  810. /* ----------------------------------------------------------------------------
  811.  * 
  812.  *   SearchTree() determines if a node's rectangular region encloses the
  813.  *   specified point in (x,y). Rather than using a brute-force search 
  814.  *   through all node rectangles of a given tree, the subtree extents
  815.  *   are used in a recursive fashion to drive the search as long as the
  816.  *   given point is enclosed in an extent. In the worst case, the search
  817.  *   time would be on the order of a brute-force search, but with complex
  818.  *   trees, this method reduces the number of visits. 
  819.  * 
  820.  *   The extent of a subtree is computed by ComputeSubTreeExtent() and is
  821.  *   stored in each node of the tree.
  822.  * 
  823.  * ----------------------------------------------------------------------------
  824.  */
  825.  
  826. int
  827. SearchTree(tree, x, y, node)
  828.      Tree *tree, **node;
  829.      int x, y;
  830. {
  831.   Tree *child;
  832.   
  833.   if (tree == NULL)
  834.     return (FALSE);
  835.  
  836.   if (PT_IN_RECT(x, y, tree->pos.x, tree->pos.y,
  837.          tree->pos.x + tree->width,
  838.          tree->pos.y + tree->height)) {
  839.     *node = tree;
  840.     return (TRUE);
  841.   }
  842.   if (tree->child && (PT_IN_EXTENT(x, y, tree->subextent))) 
  843.     FOREACH_CHILD(child, tree) {
  844.       if (SearchTree(child, x, y, node)) 
  845.     return (TRUE);
  846.     }
  847.   return (FALSE);
  848. }
  849.  
  850.  
  851. /* ----------------------------------------------------------------------------
  852.  * 
  853.  *   ExposeHandler() handles expose events in the TreeDrawingArea. This
  854.  *   function is not intelligent; it just redraws the entire contents.
  855.  * 
  856.  * ----------------------------------------------------------------------------
  857.  */
  858.  
  859. void
  860. ExposeHandler(w, client_data, event)
  861.      Widget   w;
  862.      caddr_t client_data;
  863.      XExposeEvent  *event;
  864. {
  865.   
  866.   if (event->count == 0) {
  867.     BeginFrame();
  868.       SetContours(TreeShowContourOption);
  869.       DrawTree(TheTree, New);
  870.     EndFrame();
  871.   }
  872. }
  873.  
  874.  
  875. /* ----------------------------------------------------------------------------
  876.  * 
  877.  *   ExpandCollapseNode is called to expand or collapse a node in the tree.
  878.  * 
  879.  * ----------------------------------------------------------------------------
  880.  */
  881.  
  882. void
  883. ExpandCollapseNode(node)
  884.      Tree *node;
  885. {
  886.   int        width, height;
  887.   int        old_width, old_height;
  888.   int        x_offset, y_offset;
  889.   XRectangle *rectangles;
  890.   XSegment   *segments;
  891.   int        nrectangles, nsegments;
  892.   int        expand = FALSE;
  893.   Widget     w = TreeDrawingArea;
  894.   
  895.   StatusMsg("", TRUE);
  896.   
  897.   /* hilite node so that we know where we are */
  898.   /* DrawTree will hilite it as a side effect */
  899.   if (TreeShowSteps)
  900.     node->on_path = TRUE;
  901.   
  902.   /* erase the contour before changing in the tree */
  903.   if ((TreeShowContourOption != NoContours) || TreeShowSteps) {
  904.     BeginFrame();
  905.       DrawTree(TheTree, New);
  906.     EndFrame();
  907.   }
  908.    
  909.   sprintf(strbuf, "Node `%s' selected for %s", node->label.text,
  910.       node->elision ? "expansion" : "collapse");
  911.   StatusMsg(strbuf, FALSE);
  912.   Pause(); 
  913.  
  914.   if (node->parent)
  915.     Unzip(node->parent);
  916.   else {
  917.     StatusMsg("Show entire contour", FALSE);
  918.     if (TreeShowSteps) {
  919.       BeginFrame();
  920.         DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
  921.         DrawTree(TheTree, New);
  922.       EndFrame();
  923.       Pause(); 
  924.     }
  925.   }
  926.  
  927.   /* are we collapsing a subtree? */
  928.   if (!node->elision) {
  929.     StatusMsg("Collapse subtree", FALSE);
  930.     GetSubTreeRectangles(node, &rectangles, &nrectangles, TRUE);
  931.     GetSubTreeSegments(node, &segments, &nsegments);
  932.     DissolveTree(XtDisplay(w), XtWindow(w),
  933.          rectangles, nrectangles,
  934.          segments, nsegments, TRUE);
  935.     free(rectangles);
  936.     free(segments);
  937.     Pause(); 
  938.     
  939.     StatusMsg("Replace subtree contour with leaf contour", FALSE);
  940.     node->elision = TRUE;
  941.     if (TreeShowSteps)
  942.       node->split = TRUE;    /* turned off in AnimateZip */
  943.     node->old_contour = node->contour;
  944.     node->width += ELISION_WIDTH;
  945.     LayoutLeaf(node);
  946.     BeginFrame();
  947.       SetContours(TreeShowContourOption);
  948.       DrawTree(TheTree, New);
  949.     EndFrame();
  950.     Pause();  
  951.   } else {
  952.     StatusMsg("Replace leaf contour with old subtree contour", FALSE);
  953.     if (TreeShowSteps)
  954.       node->split = TRUE;    /* turned off in AnimateZip */
  955.     RuboutLeaf(node);
  956.     node->contour = node->old_contour;
  957.     expand = TRUE;
  958.   }
  959.   
  960.   if (node->parent)
  961.     Zip(node->parent);
  962.   
  963.   ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset);
  964.   PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
  965.   GetDrawingSize(&old_width, &old_height);
  966.  
  967.   if (expand) {
  968.     SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
  969.     BeginFrame();
  970.       DrawTree(TheTree, Old);
  971.     EndFrame();
  972.     Pause(); 
  973.     StatusMsg("Move tree to new configuration", FALSE);
  974.     AnimateTree(TheTree);
  975.   } else {
  976.     /* we are shrinking or staying the same */
  977.     StatusMsg("Move tree to new configuration", FALSE);
  978.     AnimateTree(TheTree);
  979.     SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
  980.   }
  981.  
  982.   if (expand) {
  983.     StatusMsg("Expand subtree", FALSE);
  984.     node->elision = FALSE;
  985.     
  986.     /* erase elision marker */
  987.     XSetFunction(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
  988.          GXclear);
  989.     XFillRectangle(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc,
  990.            node->pos.x + node->width - ELISION_WIDTH + 1,
  991.            node->pos.y, ELISION_WIDTH, node->height + 1);
  992.     XSetFunction(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
  993.          GXcopy);
  994.     node->width -= ELISION_WIDTH;
  995.     
  996.     GetSubTreeRectangles(node, &rectangles, &nrectangles, FALSE);
  997.     GetSubTreeSegments(node, &segments, &nsegments);
  998.     /* dissolve the tree back in */
  999.     DissolveTree(XtDisplay(w), XtWindow(w),
  1000.          rectangles, nrectangles,
  1001.          segments, nsegments, FALSE);
  1002.     free(rectangles);
  1003.     free(segments);
  1004.     
  1005.     /* draw text of nodes */
  1006.     BeginFrame();
  1007.       SetContours(TreeShowContourOption);
  1008.       DrawTree(TheTree, New);
  1009.     EndFrame();
  1010.     Pause(); 
  1011.   }
  1012.   
  1013.   if (TreeShowSteps) {
  1014.     node->on_path = FALSE;
  1015.     if (node->parent)
  1016.       AnimateZip(node->parent);
  1017.     else
  1018.       node->split = FALSE;
  1019.   }
  1020.   
  1021.   /* BUG: the display isn't properly updated here! */
  1022.   /* There should probably be some code here that
  1023.      clears the tree below the node currently being 
  1024.      collapsed or expanded. Hack added 20.03.95 (torgeir@ii.uib.no). 
  1025.      I'll try to fix this later. */
  1026.  
  1027.   XClearArea(TreeDisplay, XtWindow(TreeDrawingArea), 0, 0, 0, 0, FALSE);
  1028.  
  1029.   BeginFrame();
  1030.     SetContours(TreeShowContourOption);
  1031.     DrawTree(TheTree, New);
  1032.   EndFrame();
  1033.   
  1034.   StatusMsg("Ready", TRUE);
  1035. }
  1036.  
  1037. /* ----------------------------------------------------------------------------
  1038.  * 
  1039.  *   InsertNode() handles the task of inserting a new node in the tree,
  1040.  *   at the given position with respect to 'base_node'. When 'node_pos' is
  1041.  *   either Before or After, it is assumed that 'base_node' has a parent.
  1042.  * 
  1043.  * ----------------------------------------------------------------------------
  1044.  */
  1045.  
  1046. void
  1047. InsertNode(base_node, node_pos, new_node_text)
  1048.      Tree *base_node;
  1049.      NodePosition node_pos;
  1050.      char *new_node_text;
  1051. {
  1052.   Tree *new_node;
  1053.   Tree *parent;
  1054.   Tree *sibling = NULL;
  1055.   Tree *child;
  1056.  
  1057.   int  width, height;
  1058.   int  x_offset, y_offset;
  1059.  
  1060.   StatusMsg("", TRUE);
  1061.  
  1062.   new_node = MakeNode();    /* should check for memory failure */
  1063.   SetNodeLabel(new_node, new_node_text);
  1064.   LayoutLeaf(new_node);
  1065.  
  1066.   /* figure out parent & sibling */
  1067.   if (node_pos == Child) {
  1068.     parent = base_node;
  1069.     /* find last child, if one exists */
  1070.     FOREACH_CHILD(child, parent)
  1071.       sibling = child;
  1072.   } else if (node_pos == After) {
  1073.     parent = base_node->parent;
  1074.     sibling = base_node;
  1075.   } else if (node_pos == Before) {
  1076.     parent = base_node->parent;
  1077.     FOREACH_CHILD(child, parent)
  1078.       if (child->sibling == base_node) {
  1079.     sibling = child;
  1080.     break;
  1081.       }
  1082.   }
  1083.  
  1084.   if (TreeShowSteps)
  1085.     parent->on_path = TRUE;
  1086.   
  1087.   if ((TreeShowContourOption != NoContours) ||
  1088.       TreeShowSteps) {
  1089.     BeginFrame();
  1090.       DrawTree(TheTree, New);
  1091.     EndFrame();
  1092.   }
  1093.  
  1094.   sprintf(strbuf, "Inserting `%s' as child of node `%s'",
  1095.       new_node_text, parent->label.text);
  1096.   StatusMsg(strbuf, FALSE);
  1097.   Pause(); 
  1098.    
  1099.   /* erase the contour before changing in the tree */
  1100.   
  1101.   Insert(parent, new_node, sibling);
  1102.   
  1103.   ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset);
  1104.   PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
  1105.   
  1106.   if (sibling)
  1107.     new_node->old_pos = sibling->old_pos;
  1108.   else if (new_node->sibling)
  1109.     new_node->old_pos = new_node->sibling->old_pos;
  1110.   else {
  1111.     new_node->old_pos.x = new_node->pos.x;
  1112.     new_node->old_pos.y = parent->old_pos.y;
  1113.   }
  1114.   
  1115.   if (TreeShowSteps)
  1116.     new_node->split = TRUE;
  1117.  
  1118.   SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
  1119.   BeginFrame();
  1120.     DrawTree(TheTree, Old);
  1121.   EndFrame();
  1122.   StatusMsg("Insert: add new node and contour", FALSE);
  1123.   Pause(); 
  1124.    
  1125.   StatusMsg("Move tree to new configuration", FALSE);
  1126.   AnimateTree(TheTree);
  1127.  
  1128.   if (TreeShowSteps) {
  1129.     if (parent)
  1130.       AnimateZip(parent);
  1131.   }
  1132.  
  1133.   BeginFrame();
  1134.     SetContours(TreeShowContourOption);
  1135.     DrawTree(TheTree, New);
  1136.   EndFrame();
  1137.  
  1138.   StatusMsg("Ready", TRUE);
  1139. }   
  1140.  
  1141. /* ----------------------------------------------------------------------------
  1142.  * 
  1143.  *   DeleteNode() handles the task of deleting a given node in the tree.
  1144.  * 
  1145.  * ----------------------------------------------------------------------------
  1146.  */
  1147.  
  1148. void
  1149. DeleteNode(node)
  1150.      Tree *node;
  1151. {
  1152.   Tree *parent;
  1153.  
  1154.   XRectangle *rectangles;
  1155.   XSegment   *segments;
  1156.   int         nrectangles, nsegments;
  1157.   Widget      w = TreeDrawingArea;
  1158.   int  width, height;
  1159.   int  x_offset, y_offset;
  1160.   
  1161.   StatusMsg("", TRUE);
  1162.  
  1163.   if (TreeShowSteps)
  1164.     node->on_path = TRUE;
  1165.    
  1166.   /* erase the contour before changing in the tree */
  1167.   if ((TreeShowContourOption != NoContours) ||
  1168.       TreeShowSteps) {
  1169.     BeginFrame();
  1170.       DrawTree(TheTree, New);
  1171.     EndFrame();
  1172.   }
  1173.  
  1174.   sprintf(strbuf, "Node `%s' selected for deletion", node->label.text);
  1175.   StatusMsg(strbuf, FALSE);
  1176.   Pause(); 
  1177.   
  1178.   parent = node->parent;
  1179.   
  1180.   if (parent)
  1181.     Unzip(parent);
  1182.   else
  1183.     TheTree = NULL;        /* delete root of tree */
  1184.  
  1185.   /* fade out deleted subtree */
  1186.   StatusMsg("Delete subtree", FALSE);
  1187.   GetSubTreeRectangles(node, &rectangles, &nrectangles, TRUE);
  1188.   GetSubTreeSegments(node, &segments, &nsegments);
  1189.   DissolveTree(XtDisplay(w), XtWindow(w),
  1190.            rectangles, nrectangles,
  1191.            segments, nsegments, TRUE);
  1192.   free(rectangles);
  1193.   free(segments);
  1194.  
  1195.   Delete(node);
  1196.  
  1197.   BeginFrame();
  1198.   if (TheTree) 
  1199.     DrawTree(TheTree, New);
  1200.   EndFrame();
  1201.   Pause(); 
  1202.  
  1203.   if (parent)
  1204.     Zip(parent);
  1205.   
  1206.   if (TheTree) {
  1207.     ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset);
  1208.     PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
  1209.     StatusMsg("Move tree to new configuration", FALSE);
  1210.     AnimateTree(TheTree);
  1211.     SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
  1212.     Pause(); 
  1213.  
  1214.     if (TreeShowSteps) {
  1215.       if (parent)
  1216.     AnimateZip(parent);
  1217.     }
  1218.  
  1219.     BeginFrame();
  1220.       SetContours(TreeShowContourOption);
  1221.       DrawTree(TheTree, New);
  1222.     EndFrame();
  1223.  
  1224.   }
  1225.  
  1226.   StatusMsg("Ready", TRUE);
  1227. }
  1228.  
  1229.  
  1230. /* ----------------------------------------------------------------------------
  1231.  * 
  1232.  *   ResetLabels() is called when the TreeAlignNodes mode is changed. 
  1233.  *   When TreeParentDistance changes, the node width changes, so this
  1234.  *   function forces each node's width to be recomputed. 
  1235.  * 
  1236.  * ----------------------------------------------------------------------------
  1237.  */
  1238.  
  1239. ResetLabels(tree)
  1240.      Tree *tree;
  1241. {
  1242.   Tree *child;
  1243.   
  1244.   SetNodeLabel(tree, tree->label.text);
  1245.   FOREACH_CHILD(child, tree)
  1246.     ResetLabels(child);
  1247. }
  1248.  
  1249.  
  1250. /* ----------------------------------------------------------------------------
  1251.  * 
  1252.  *   SetupTree() handles the task of setting up the specified tree in 
  1253.  *   the drawing area.
  1254.  * 
  1255.  * ----------------------------------------------------------------------------
  1256.  */
  1257.  
  1258. void
  1259. SetupTree(tree)
  1260.      Tree *tree;
  1261. {
  1262.   int width, height;
  1263.   int x_offset, y_offset;
  1264.   
  1265.   LayoutTree(tree);
  1266.   ComputeTreeSize(tree, &width, &height, &x_offset, &y_offset);
  1267.   PetrifyTree(tree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
  1268.   SetDrawingTree(tree);
  1269.   SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
  1270.   BeginFrame();
  1271.     SetContours(TreeShowContourOption);
  1272.     DrawTree(tree, New);
  1273.   EndFrame();
  1274. }
  1275.  
  1276.  
  1277.  
  1278.  
  1279.  
  1280.  
  1281.